package algorithm;

public class T00427 {
    public static void main(String[] args) {
        int[][] grid = {{0,1},{1,0}};
        new Solution().construct(grid);
    }

    static class Solution {
        public Node construct(int[][] grid) {
            return constructNode(grid, 0, 0, grid.length);
        }

        public Node constructNode(int[][] grid, int r, int l, int n) {
            int sum = 0;
            for (int i = r; i < r + n; i++) {
                for (int j = l; j < l + n; j++) {
                    sum += grid[i][j];
                }
            }
            if (sum == 0 || sum == n * n) {
                return new Node(sum != 0, true);
            }
            Node node = new Node(false, false);
            int nn = n >> 1;
            node.topLeft = constructNode(grid, r, l, nn);
            node.topRight = constructNode(grid, r, l + nn, nn);
            node.bottomLeft = constructNode(grid, r + nn, l, nn);
            node.bottomRight = constructNode(grid, r + nn, l + nn, nn);
            return node;
        }
    }

    static class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;

        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }
}
